from functools import cache
from typing import List


class Solution:
    def jump(self, nums: List[int]) -> int:
        n = len(nums)

        @cache
        def dfs(i):
            if i == n - 1:
                return 0
            # 当前值为0，无效，结束跳跃
            if nums[i] == 0:
                return float('inf')
            min_jumps = float('inf')
            for j in range(1, nums[i] + 1):
                if i + j < n:
                    min_jumps = min(min_jumps, 1 + dfs(i + j))
            return min_jumps
        return dfs(0)